map_data = [
    "###############################",
    "# p    ## #    #   #  # # #   #",
    "# # # ### # ##### # # ####### #",
    "#   #     ###  #      #   # # #",
    "# # # # # ### # ##### # # # ###",
    "####       # ##  #  #         #",
    "### ### # # # # # ### ### # # #",
    "#                             #",
    "######### # # # ##### # # # # #",
    "#    4 #  #       #           #",
    "# ####### ### # ### # # # # # #",
    "#           #   #  #          #",
    "###############################"
]


def calculate_probability(x):
    rows = len(map_data)
    cols = len(map_data[0])
    count = 0

    # 初始化概率数组
    probabilities = [[0.0] * cols for _ in range(rows)]

    # 找到起始位置和目标位置
    start_pos = None
    p_pos = None
    for i in range(rows):
        for j in range(cols):
            if map_data[i][j] == "4":
                start_pos = (i, j)
            elif map_data[i][j] == "p":
                p_pos = (i, j)

    if start_pos is None or p_pos is None:
        return count
    print(p_pos)
    print(start_pos)

    # 迭代计算概率
    while True:
        updated = False

        for i in range(rows):
            for j in range(cols):
                if map_data[i][j] == " ":
                    # 计算向上、下、左、右移动的概率
                    up_prob = probabilities[i - 1][j] if i > 0 else 0.0
                    down_prob = probabilities[i + 1][j] if i < rows - 1 else 0.0
                    left_prob = probabilities[i][j - 1] if j > 0 else 0.0
                    right_prob = probabilities[i][j + 1] if j < cols - 1 else 0.0

                    # 计算向 p 移动的概率
                    to_p_prob = x * (up_prob + down_prob) / 2.0 + x * (left_prob + right_prob) / 2.0

                    # 计算随机移动的概率
                    random_prob = (1 - x) * (up_prob + down_prob + left_prob + right_prob) / 4.0

                    # 更新概率数组中的值
                    new_prob = max(to_p_prob, random_prob)
                    if new_prob != probabilities[i][j]:
                        probabilities[i][j] = new_prob
                        updated = True

        if not updated:
            break

    return count


# 遍历不同的 x 值，计算移动到 p 处的最大概率
max_probability = 0.0
max_x = 0.0

for x in range(101):
    x = x / 100.0
    probability = calculate_probability(x)

    if probability > max_probability:
        max_probability = probability
        max_x = x

print(f"The maximum probability is {max_probability} when x = {max_x}")
